// https://www.lintcode.com/problem/convert-bst-to-greater-tree/description
// 661. 把二叉搜索树转化成更大的树
// 给定二叉搜索树(BST)，将其转换为更大的树，使原始BST上每个节点的值都更改为在原始树中大于等于该节点值的节点值之和(包括该节点)。

// 样例
// Given a binary search Tree `{5,2,13}｀:

//               5
//             /   \
//           2     13
// Return the root of new tree

//              18
//             /   \
//           20     13
          
          

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: the root of binary tree
     * @return: the new root
     */
    int sum = 0;
    TreeNode * convertBST(TreeNode * root) {
        traverse(root);
        return root;
    }
    
    // 这边递归是DFS
// • DFS的两种理解方式：
// 1. 按照实际执行顺序模拟 （适合枚举型DFS）
// 2. 按照DFS的定义宏观理解 （适合分治型DFS）
    void traverse(TreeNode * root)
    {
        if (!root)
        {
            return;
        }
        traverse(root->right);
        sum += root->val;
        root->val = sum;
        traverse(root->left);
    }
};